package binarySearch;

/**
 * @author pengfei.hpf
 * @date 2020/3/10
 * @verdion 1.0.0
 * 875. 爱吃香蕉的珂珂
 * 珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
 *
 * 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
 *
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 *
 * 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
 *
 *
 *
 * 示例 1：
 *
 * 输入: piles = [3,6,7,11], H = 8
 * 输出: 4
 * 示例 2：
 *
 * 输入: piles = [30,11,23,4,20], H = 5
 * 输出: 30
 * 示例 3：
 *
 * 输入: piles = [30,11,23,4,20], H = 6
 * 输出: 23
 *
 *
 * 提示：
 *
 * 1 <= piles.length <= 10^4
 * piles.length <= H <= 10^9
 * 1 <= piles[i] <= 10^9
 */
public class MinEatingSpeed {
    public int minEatingSpeed(int[] piles, int H) {
        if(piles == null || piles.length == 0){
            return 0;
        }
        int left = 1;
        int right = getMax(piles);
        while(left < right){
            int mid = left + (right - left)/2;
            if(canFinish(piles, mid, H)){
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private int getMax(int[] piles){
        int max = 0;
        for(int i: piles){
            max = Math.max(max, i);
        }
        return max;
    }

    private boolean canFinish(int[] piles, int sp, int H){
        int time = 0;
        for(int i: piles){
            time += i/sp + (i%sp == 0? 0 : 1);
        }
        return time <= H;
    }
}
